When a new record is to be inserted into a table in a database management system (DBMS), a storage manager must find a sufficiently large block of storage for this record. A storage manager has several contradictory goals: to allocate a block quickly, to place related data in some proximity, to avoid or minimize internal and external fragmentation.
To achieve a good speed of record allocation and a low internal fragmentation, some storage managers partition a new chunk of storage into equally sized blocks and use that region of storage only for the allocation of blocks of that particular size. The disadvantage of this approach is external fragmentation, and if the size of such a block is not popular, the remainder of the storage block will not be used.
To achieve a faster query time, some storage managers place related data on the same storage block. The disadvantage of this approach is that if there are not enough related records, some of the storage goes unused. To mitigate this, some storage allocators try to use the remaining storage for records that are not related. However, this will largely reduce the effectiveness and the original purpose of the scheme (that is, to try to provide with a quick access to related records) because the new related records will have to be placed elsewhere. Placing related records together is often called clustering.
Some database records may contain a portion which has a variable length. In addition, to reduce the amount of storage, users may want to compress the data of records. As a result, different records of a relational table (which normally all have the same size) may have a different size in a compressed form depending on the nature (compressibility) of data. Hence, related records may have different sizes and naive storage allocation methods that operate on fixed sized blocks are impractical.
Additionally, existing approaches include a one-dimensional view of available storage properties and/or attributes for search, that is, only one search property is considered such as either a size or a key value, but not both.